package 链表;
//https://www.nowcoder.com/practice/02bf49ea45cd486daa031614f9bd6fc3?tpId=295&tqId=1073463&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj
public class BM14_链表的奇偶重排 {

	public static void main(String[] args) {
		BM14_链表的奇偶重排 test = new BM14_链表的奇偶重排();
		//{2,1,3,5,6,4,7}  {1,2,3,4,5,6} 
		ListNode node1 = new ListNode(2);
		ListNode node2 = new ListNode(1);
		ListNode node3 = new ListNode(3);
		ListNode node4 = new ListNode(5);
		ListNode node5 = new ListNode(6);
		ListNode node6 = new ListNode(4);
		ListNode node7 = new ListNode(7);
		node1.next = node2;
		node2.next = node3;
		node3.next = node4;
		node4.next =node5;
		node5.next =node6;
		node6.next = node7;
		System.out.println(test.oddEvenList(node1));
	}
	
	public ListNode oddEvenList (ListNode head) {
		if(head == null) return head;
		//odd开头指向第一个节点
		ListNode odd = head;
		//even开头指向第二个节点，可能为空
		ListNode even = head.next;
		//指向even开头
        ListNode evenHead = even;
        while(even != null && even.next != null) {
        	//odd连接even的后一个，即奇数位
        	odd.next = even.next;
        	//odd进入后一个奇数位
        	odd = odd.next;
        	//even连接后一个奇数的后一位，即偶数位
        	even.next = odd.next;
        	//even进入后一个偶数位
        	even = even.next;
        }
        odd.next = evenHead;
        return head;
    }
}
